# 给你一个有序数组 nums ，请你 原地 删除重复出现的元素，使每个元素 最多出现两次 ，返回删除后数组的新长度。
#  不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
#
#  示例 1：
# 输入：nums = [1,1,1,2,2,3]
# 输出：5, nums = [1,1,2,2,3]
# 解释：函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
#
#  示例 2：
# 输入：nums = [0,0,1,1,1,1,2,3,3]
# 输出：7, nums = [0,0,1,1,2,3,3]
# 解释：函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3 。 不需要考虑数组中超出新长度后面的元素。
from typing import List


class Solution:
    def removeDuplicates(self, nums: List[int], k: int = 2) -> int:
        """
        双指针
        left指针指向当前已经处理过的的最后一个元素的位置
        right指向已经遍历到的位置
        由于数组已经是有序的那么
        如果有: nums[i - k] == nums[i]
        则: 一定有 nums[i - k] = nums[i - k + 1] = nums[i - k + 2] ... = nums[i]

        :param nums:
        :param k: 需要保留的元素最大重复个数,默认为 2
        :return:
        """
        numLen = len(nums)
        if numLen <= 2:
            return numLen
        left = right = 2
        while right < numLen:
            if nums[left - k] != nums[right]:
                nums[left] = nums[right]
                left += 1
            right += 1
        return left


if __name__ == "__main__":
    nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
    print(Solution().removeDuplicates(nums))
    print(nums)
